package leetCode.daily;

import org.junit.Test;

import java.util.LinkedList;
import java.util.List;

public class Code_1035 {
    @Test
    public void test() {
        int lines = maxUncrossedLines(new int[]{1, 3, 7, 1, 7, 5}, new int[]{1, 9, 2, 5, 1});
        System.out.println(lines);
    }

    /**
     * 本质是求最长公共子序列。（K条连线上下端点的顺序是一致的）
     * dp[i][j]=nums1前i个数字和nums2前j个数字的最长公共子序列长度。
     * 1.dp[i][j] = dp[i-1][j-1]+1 if nums1[i-1]==nums2[j-1]
     * 2.dp[i][j] = max(dp[i][j-1], dp[i-1][j]) if nums1[i]!=nums2[j]
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] tmp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i <= nums1.length; ++i) {
            for (int j = 1; j <= nums2.length; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    tmp[i][j] = tmp[i - 1][j - 1] + 1;
                } else {
                    tmp[i][j] = Math.max(tmp[i - 1][j], tmp[i][j - 1]);
                }
            }
        }
        return tmp[nums1.length][nums2.length];
    }
}
